//你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。 
//
// 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 
//
// 示例 1: 
//
// 
//输入: 二叉树: [1,2,3,4]
//       1
//     /   \
//    2     3
//   /    
//  4     
//
//输出: "1(2(4))(3)"
//
//解释: 原本将是“1(2(4)())(3())”，
//在你省略所有不必要的空括号对之后，
//它将是“1(2(4))(3)”。
// 
//
// 示例 2: 
//
// 
//输入: 二叉树: [1,2,3,null,4]
//       1
//     /   \
//    2     3
//     \  
//      4 
//
//输出: "1(2()(4))(3)"
//
//解释: 和第一个示例相似，
//除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
// 
// Related Topics 树 深度优先搜索 字符串 二叉树 
// 👍 288 👎 0

package com.cute.leetcode.editor.cn;
public class ConstructStringFromBinaryTree {
    public static void main(String[] args) {
        Solution solution = new ConstructStringFromBinaryTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public String tree2str(TreeNode root) {
            StringBuilder res = new StringBuilder();
            prefix(root, res);
            return res.substring(1, res.length() - 1);
        }
        // 这个是在当前节点处理下一个节点的括号
        private void prefix1(TreeNode node, StringBuilder s){
            s.append(node.val);
            if (node.left == null && node.right == null) return;
            if (node.left != null && node.right != null) {
                s.append("(");
                prefix1(node.left, s);
                s.append(")");
                s.append("(");
                prefix1(node.right, s);
                s.append(")");
            }else if (node.left == null){
                s.append("()(");
                prefix1(node.right, s);
                s.append(")");
            }else {
                s.append("(");
                prefix1(node.left, s);
                s.append(")");
            }
        }

        /**
         * 当前节点处理括号，最后结果将头尾括号去掉即可
         */
        private void prefix(TreeNode node, StringBuilder s){
            s.append("(").append(node.val);
            if (node.left != null) prefix(node.left, s);
            else if (node.right != null) s.append("()");// 左节点为null右节点不为null时需添加括号
            if (node.right != null) prefix(node.right, s);
            s.append(")");
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
